Masala #0797

Satr chapdan o’ngga o’qilsa ham, o’ngdan chapga o’qilsa ham bir xil bo’lsa bunday satr palindrom satr deb ataladi. Masalan : «a», «aa», «obbo», «aka» va «uzbekezbu» satrlari palindrom satrdir.
\(S\) satrning qism satrlari deb shu satrning barcha \(1 ≤ i ≤ j ≤ |S|\) juftliklar uchun \(S_i, S_{i+1}, \dots , S_j\) ketma-ketlikdan tashkil topgan satrlarga aytiladi. Misol uchun «obbo» satrida «o», «b», «b», «o», «ob», «bb», «bo», «obb», «bbo», «obbo» qism satrlar mavjud.

Sizga dastlab \(S\) bo’sh satr berilgan. Siz \(S\) satri ustada \(Q\) ta so’rovni berilish tartibida bajarishingiz kerak.
Har bir so’rovda sizga \(c(c ∈ [ − , a − z])\) belgisi kiritiladi.

✦ Agar c = ′−′ bo’lsa siz \(S\) satrning oxirgi belgisini o’chirishingiz kerak(bunday holda \(S\) satrda o’chirish uchun belgi borligi kafolotlanadi).

✦ Agar \(c ∈ [a − z]\) bo’lsa siz \(S\) satrning oxiriga berilgan belgini qo’shishingiz kerak. Har bir so’rovdan so’ng \(S\) satrining qism satrlaridan nechtasi palindrom ekanligini chop eting!

Birinchi satrda bitta butun son, so’rovlar soni \(Q(1 ≤ Q ≤ 10^4)\) kiritiladi.
Ikkinchi satrda Q ta belgi, ya’ni har bir so’rov uchun c belgisi bir - beridan ajratilmagan holda kiritiladi.

Yagona satrda probel bilan ajratilgan holda Q ta butun son, har bir so’rovdan so’ng S satrining qism satrlaridan nechtasi palindrom ekanligini chop etilsin!